﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0073_IsSubtree : IAlgorithm
    {
        // 572. 另一棵树的子树

        // 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
        // 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

        // 提示：
        //  root 树上的节点数量范围是[1, 2000]
        //  subRoot 树上的节点数量范围是[1, 1000]
        //  -10^4 <= root.val <= 10^4
        //  -10^4 <= subRoot.val <= 10^4


        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public bool IsSubtree(TreeNode root, TreeNode subRoot)
        {
            return DFS(root, subRoot);
        }
        public bool DFS(TreeNode s, TreeNode t)
        {
            if (s == null)
            {
                return false;
            }
            return Check(s, t) || DFS(s.left, t) || DFS(s.right, t);
        }
        public bool Check(TreeNode s, TreeNode t)
        {
            if (s == null && t == null)
            {
                return true;
            }
            if (s == null || t == null || s.val != t.val)
            {
                return false;
            }
            return Check(s.left, t.left) && Check(s.right, t.right);
        }
    }
}
